无糖乌龙

没有明天的烂人

CodeForces Round 642 Div3 A~F题解

发布于 2020-05-15 | 分类于 CodeForces | 20分钟 | 4008字数

前面四题都比较简单，搞快一点

A:比较显然的的是，n是1的时候答案是0，n是2的时候答案是m，其余的情况观察样例最多是2m

typedef long long ll;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int n,m;scanf("%d%d",&n,&m);
		if(n == 1)	printf("0\n");
		else if (n == 2)	printf("%d\n",m);
		else printf("%d\n",2 * m);
    }
    return 0;
}

B：开两个堆，一共迭代最多K次，每次从a里面找出最小的，从b里面找出最大的，把两者交换一下，如果发现交换没有价值的时候说明可以提前退出了。

typedef long long ll;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int n,k,x;scanf("%d%d",&n,&k);
		priority_queue<int,vector<int>,greater<int> >pa;
		priority_queue<int,vector<int>,less<int> > pb;
		for(int i = 1;i <= n;++i)
			scanf("%d",&x),pa.push(x);
		for(int i = 1;i <= n;++i)
			scanf("%d",&x),pb.push(x);
		for(int i = 1;i <= k;++i)
		{
			int ta = pa.top();pa.pop();
			int tb = pb.top();pb.pop();
			if(ta < tb)
			{
				pa.push(tb);
				pb.push(ta);
			}
			else
			{
				pa.push(ta);
				pb.push(tb);
				break;
			}
		}
		int res = 0;
		while(!pa.empty())
		{
			res += pa.top();
			pa.pop();
		}
		printf("%d\n",res);
    }
    return 0;
}

C：可以猜出一个结论，那就是想要所有距离最短，肯定是所有的都最短，那么就是所有的点都往中心走就可以了，题目又刚好说n一定是奇数，于是可以果断猜出结论就是全部往中心走。接着可以发现数字的规律是一圈一圈增大的，中心是0，往外环绕一圈的是1，再往外就是2，因此可以推出规律：对于当前在考虑的数字ii，它一共出现了⌊i/2⌋∗8\lfloor i/2\rfloor * 8次，总数是⌊i/2⌋\lfloor i/2\rfloor个，因此答案就是
res = ∑i=1,i是奇数n⌊i/2⌋∗8∗⌊i/2⌋\sum\limits_{i=1,i是奇数}^n\lfloor i/2\rfloor * 8 * \lfloor i/2\rfloor

typedef long long ll;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		ll n;scanf("%lld",&n);
		ll res = 0;
		for(ll i = 1;i <= n;i += 2)
			res += (i / 2) * 8 * (i / 2);
		printf("%lld\n",res);
    }	
    return 0;
}

D:维护一个堆，里面的元素带两个值，第一个是总长度len，第二个是左端点l。每次从堆里面取出len最大的元素，以及l最小的元素，注意：由于第一关键字按最大的排序，因此l在插入的时候是插入的负l，做的时候要转换。

typedef long long ll;
typedef pair<int,int> pii;//len&lp
const int N = 2e5+7;
int res[N];
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
    	int n;scanf("%d",&n);
		if(n == 1)
		{
			printf("1\n");
			continue;
		}
		priority_queue<pii> pq;
		pq.push({n,-1});
		int i = 1;
		while(!pq.empty())
		{
			pii t = pq.top();pq.pop();
			int len = t.first,l = -t.second;
			int r = l + len - 1;
			int pos = (r - l + 1) % 2 == 1 ? (l + r) / 2 : (l + r - 1) / 2;
			res[pos] = i++;
    		//left
    		if(pos - l > 0)	pq.push({pos - l,-l});
    		//right
    		if(r - pos > 0) pq.push({r - pos,-pos - 1});
    	}
    	for(int i = 1;i <= n;++i)	printf("%d ",res[i]);
    	puts("");
    }
    return 0;
}

E：
题意：给定一个长度为nn的只有01的字符串，和一个数值kk。你可以执行一个操作：选择字符串中的一个数字让他反转，现在要求字符串中每一对1的之间恰好有k−1k-1个0，问最少要执行多少次操作。
注意：字符串并不是一个环形的，不要求第一个必须也跟最后一个环上满足，同时你也可以让所有的11变成0，这也是满足题意得。
数据范围：1≤T≤250001 \leq T \leq 25000组数据
1≤n≤1061 \leq n \leq 10^6且1≤k≤n1 \leq k \leq n
分析：如果我们把原字符串S分成K组，按i...i+k...i+2k...i...i+k...i+2k...分，可以发现，对于一个合法方案来说，一定是只有其中某一组可以存在11，而其他的所有组都不能存在11，必须全部划到00。因此第一步首先分组并求出每一组自身的数值和，数值和等价于让这一组数全部推成00的代价。进而，我们可以枚举每一组数作为能存在11的序列的时候，所需要的总代价，这分为两个部分：一是把其他序列推成00的代价，二是把当前这个序列推成带有一且合法的序列，前面一个部分比较好算，计算所有序列的和再把当前这一组的和挖掉就可以了，对于第二部分，首先一个合法的序列是形如一段连续的00，一段连续的11，一段连续的0这样的序列考虑dp，记fpf_p是当前字符串p中，让末尾的1出现在p位置的最小代价，不难发现dp转移只有两种来源，一是pp位置就是第一个11，这时fp=∑[0,p−1]f_p = \sum[0,p-1]，即让前面推成0的代价；二是前面有11，当前的pp是末尾，此时fp=fp−1f_p = f_{p - 1}，这里要注意的是，如果t[p]t[p]不是11，则需要对之额外增加11的代价。
那么，记res[i]res[i]是把ii组字符串作为存在11序列的代价，可以推出:
res[i]={∑[0,len−1]最坏情况整个序列推到0min(part[p])一般情况res[i]=\begin{cases}\sum[0,len - 1]&最坏情况整个序列推到0\\min(part[p])&一般情况\end{cases}
其中part[p]=fp+∑[0,len−1]−∑[p,len−1]part[p] = f_p + \sum[0,len - 1] - \sum[p,len - 1] 即末尾p之前的代价和p之后推到0的代价总和，min(part[p])min(part[p])表示在p∈[0,len−1]p∈[0,len-1]中取最小值。
最后，实际的答案rres=min(res[i]+所有总和−当前i的和)rres = min(res[i] + 所有总和 - 当前i的和)
(我的代码实现比较复杂，如果能自己写出来更好)

typedef long long ll;
const int N = 1e6+7;
char s[N];

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int n,k;scanf("%d%d",&n,&k);
		scanf("%s",s);
		int tot = 0;
		for(int i = 0;i < n;++i)	tot += s[i] - '0';
    	vector<string> groups(k);
    	for(int i = 0;i < n;++i)
    		groups[i % k].push_back(s[i]);
    	int res = 1e9+7;
    	for(int j = 0;j < k;++j)
    	{
    		string& s = groups[j];
    		int sz = s.size();
    		int ptot = 0,fres,pref = 0;
    		for(int i = 0;i < sz;++i)	ptot += s[i] - '0';
    		fres = ptot;
    		vector<int> fp(sz,0);
    		for(int i = 0;i < sz;++i)
    		{
    			fp[i] = 1 - int(s[i] == '1');
    			if(i > 0)	fp[i] = min(fp[i - 1],pref) + (s[i] != '1');
    			pref += s[i] == '1';
    			fres = min(fres,fp[i] + ptot - pref);
    		}
    		res = min(res,fres + tot - ptot);
    	}
    	
    	printf("%d\n",res);
    }
    return 0;
}

F：
题意： 有一个nxmnxm的棋盘，棋盘上有一些数字a[i][j]a[i][j]，起始时你在(1,1)(1,1)上，你想要移动到(n,m)(n,m)这个位置上，每次移动，你只能从当前位置向右走和向下走，且必须满足目标位置的数字是刚好等于当前位置上的数+1+1的。为了保证你可以从起始位置走到终点，你可以在走之前执行若干次以下这种操作：把某个位置上的数−1-1，问你能从起始位置走到终点位置，最少需要的操作是多少次。
注意：你可以修改起始位置的数值，数值也可以修改到负数。
数据范围：T组数据 1≤T≤1001 \leq T \leq 100
1≤n,m≤1001 \leq n,m \leq 100
1≤a[i][j]≤10151 \leq a[i][j] \leq 10^{15}
分析：最少次数，联想到bfs，但是这个题单纯的从起点搜到终点肯定没法对值进行操作，进一步的可以贪心想到可能会有一个作为基准的值：对于某一个修改方案来说，一定至少存在某一个点(x,y)(x,y)的值是没有修改过的，因为假如所有的点都被修改了，那么这个所有数都修改的方案，一定对应着某一个至少有一个数没有修改过的方案（把所有数都+1相当于没加），并且后者的操作次数更少，因此对于某个合法的修改方案来说一定至少有一个没有被修改的值。这启发我们可以枚举每个位置的值作为基准，作为那个前后修改过后不变的值，进而推出所有其他的值。
假设这个棋盘是有(0,0)(0,0)位置的（这么做的原因是相对坐标比较好算，从题目给的那个起始开始算要算一些加一减一的问题），设b[i][j]b[i][j]表示，点(i,j)(i,j)修改到合法方案时的值；点(x,y)(x,y)是当前枚举的那个不动点，则对于不动点来说，有：b[x][y]=a[x][y]=b[0][0]+x+yb[x][y] = a[x][y] = b[0][0] + x + y，因为每次移动的时候都必须是下一个位置值恰好增大11，所以坐标之和就是差，故可以根据这个式子直接推出b[0][0]=b[x][y]−x−yb[0][0] = b[x][y] - x - y，同时对于其他点，最终要修改到的值也就可以推出来了。
接下来枚举不动点，从每个不动点开始搜bfs就可以了，不过这里要从不动点分别往左上和右下搜索。对于下一个拓展的位置(a,b)(a,b)来说，必须要满足a[a][b]≥b[x][y]a[a][b] \geq b[x][y]，才可以拓展，并且新的路径和就是修改次数，直接加进去就可以，最终答案就是dist[1][1]+dist[n][m]dist[1][1] + dist[n][m]。
这里在具体实现上来说，需要使用优先队列bfs，元素是一对坐标值，这里重载了pair<int,int>pair<int,int>的比较器，使之top()top()就是当前dist[x][y]dist[x][y]最小的值。

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define x first
#define y second
const int N = 105;
ll INF = 0x3f3f3f3f3f3f3f3f,res;
ll dist[N][N];

struct cmp
{
	bool operator()(const pii& a,const pii& b)
	{
		return dist[a.x][a.y] > dist[b.x][b.y];
	}
};
ll a[N][N];
int n,m;

void bfs(int sx,int sy)
{
	memset(dist,0x3f,sizeof dist);
	priority_queue<pii,vector<pii>,cmp> pq;
	pq.push({sx,sy});
	dist[sx][sy] = 0;
	ll b = a[sx][sy] - sx - sy;
	while(!pq.empty())
	{
		pii t = pq.top();pq.pop();
		int x = t.x,y = t.y;
		if(x - 1 >= 0 && a[x - 1][y] >= b + x - 1 + y
		&& dist[x - 1][y] > dist[x][y] + a[x - 1][y] - (b + x - 1 + y))
		{
			dist[x - 1][y] = dist[x][y] + a[x - 1][y] - (b + x - 1 + y);
			pq.push({x - 1,y});
		}
		if(y - 1 >= 0 && a[x][y - 1] >= b + x + y - 1
		&& dist[x][y - 1] > dist[x][y] + a[x][y - 1] - (b + x + y - 1))
		{
			dist[x][y - 1] = dist[x][y] + a[x][y - 1] - (b + x + y - 1);
			pq.push({x,y - 1});
		}
	}
	pq.push({sx,sy});
	while(!pq.empty())
	{
		pii t = pq.top();pq.pop();
		int x = t.x,y = t.y;
		if(x + 1 <= n && a[x + 1][y] >= b + x + 1 + y
		&& dist[x + 1][y] > dist[x][y] + a[x + 1][y] - (b + x + 1 + y))
		{
			dist[x + 1][y] = dist[x][y] + a[x + 1][y] - (b + x + 1 + y);
			pq.push({x + 1,y});
		}
		if(y + 1 <= m && a[x][y + 1] >= b + x + y + 1
		&& dist[x][y + 1] > dist[x][y] + a[x][y + 1] - (b + x + y + 1))
		{
			dist[x][y + 1] = dist[x][y] + a[x][y + 1] - (b + x + y + 1);
			pq.push({x,y + 1});
		}
	}
	res = min(res,dist[1][1] + dist[n][m]);
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		scanf("%d%d",&n,&m);
    	for(int i = 1;i <= n;++i)
    		for(int j = 1;j <= m;++j)
    			scanf("%lld",&a[i][j]);
    	res = INF;
    	for(int i = 1;i <= n;++i)
    		for(int j = 1;j <= m;++j)
    			bfs(i,j);
    	printf("%lld\n",res);
    }
    return 0;
}

DP solution:
这个题目规定的行进路线是从起始点到最右下角，同时只能向右和向下走，这可以联系到一个很简单的DP路径问题：每个点上的权值都是固定的，从某个点走到另一个点，如果合法则增加一个值，如果不合法那么下一步的位置上就是障碍。
因此在上面分析过后，事实上DP解也是比较好想到的，首先也是枚举所有点作为基准的情况，其次每次从(1,1)(1,1)开始往右方向和下方向递推，如果合法就记录当前位置权值+1和下一个点的差值，否则就直接设置成INFINF，最终答案是所有到最终点的最小权值和的最小值。
DP：
状态：f[x][y]f[x][y]表示走到(x,y)(x,y)最小的花费。
入口：初始f[1][1]=b[0][0]+2其余INFf[1][1] = b[0][0] + 2 其余INF，若起始点无法到达(a[1][1]<b+2a[1][1] < b+2)则直接返回INFINF
出口：minf[n][m]min{f[n][m]}
转移：要注意为横和竖边角单独处理，其余的时候有：
当a[x][y]>b+x+ya[x][y] > b + x + y时，当前(x,y)(x,y)是可以到达的，遂更新
dist[x][y]=a[x][y]−(b+x+y)+min(dist[x−1][y],dist[x][y−1])dist[x][y] = a[x][y] - (b + x + y) + min(dist[x - 1][y],dist[x][y - 1])

typedef long long ll;
typedef pair<int, int> pii;
#define x first
#define y second
const int N = 105;
ll INF = 0x3f3f3f3f3f3f3f3f, res;
ll dist[N][N];

ll a[N][N];
int n, m;
ll dp(int sx, int sy)
{
    memset(dist, 0x3f, sizeof dist);
    ll b = a[sx][sy] - sx - sy;
    if(a[1][1] < b + 2)	return INF;
    dist[1][1] = a[1][1] - (b + 2);
    for(int i = 2;i <= m;++i)	
    	if(a[1][i] >= b + 1 + i)
    		dist[1][i] = a[1][i] - (b + 1 + i) + dist[1][i - 1];
    for(int i = 2;i <= n;++i)
    	if(a[i][1] >= b + i + 1)
    		dist[i][1] = a[i][1] - (b + i + 1) + dist[i - 1][1];
    for (int i = 2; i <= n; ++i)
        for (int j = 2; j <= m; ++j)
            if (a[i][j] >= b + i + j)
                dist[i][j] = a[i][j] - (b + i + j) + min(dist[i - 1][j],dist[i][j - 1]);
    return dist[n][m];
}
int main()
{
    int T; scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                scanf("%lld", &a[i][j]);
        res = INF;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                res = min(dp(i, j), res);
        printf("%lld\n", res);
    }
    return 0;
}

此外，上面的代码是使用的(x,y)(x,y)有哪些状态组成，如果写成出边转移的方式的话会更简单一些，不需要像上面那样写特殊处理

ll dp(int sx, int sy)
{
    memset(dist, 0x3f, sizeof dist);
    ll b = a[sx][sy] - sx - sy;
    if(a[1][1] < b + 2)	return INF;
    dist[1][1] = a[1][1] - (b + 2);
    for(int i = 1;i <= n;++i)
        for(int j = 1;j <= m;++j)
        {
            if(i + 1 <= n && a[i + 1][j] >= b + i + 1 + j)
                dist[i + 1][j] = min(dist[i + 1][j],a[i + 1][j] - (b + i + 1 + j) + dist[i][j]);
            if(j + 1 <= m && a[i][j + 1] >= b + i + j + 1)
                dist[i][j + 1] = min(dist[i][j + 1],a[i][j + 1] - (b + i + j + 1) + dist[i][j]);
        }
    return dist[n][m];
}
# CodeForces
环形结构上的动态规划 上一篇
Atcoder abc167 题解 下一篇
Powered by Gridea | © 2019-2020 Theme By HsxyHao
没有明天的人
0%